'''
Created on 2010-3-3

@author: Administrator
'''
import sys
from jolly.datastructures.HashTable import HashTable
from jolly.datastructures.Array import Array
from jolly.datastructures.LinkedList import LinkedList
from jolly.datastructures.Iterator import Iterator
from jolly.datastructures.Visitor import Visitor

class ChainedHashTable(HashTable):
    '''
    Hash table implemented using an array of linked lists.
    '''


    def __init__(self, length):
        '''
        (ChainedHashTable, int) -> None
        Constructs a chained hash table with the given length.
        '''
        super(ChainedHashTable, self).__init__()
        self._array=Array(length)
        for i in xrange(len(self._array)):
            self._array[i] = LinkedList()
    
    def __len__(self):
        '''
        (ChainedHashTable) -> int
        Returns the length of this chained hash table.
        '''
        return len(self._array)
    
    def purge(self):
        '''
        (ChainedHashTable) -> None
        Purges this chained hash table.
        '''
        for i in xrange(len(self._array)):
            self._array[i].purge()
        self._count=0
    
    def insert(self, obj):
        '''
        (ChainedHashTable, Object) -> None
        Inserts the given object into this chained hash table.
        '''
        self._array[self.h(obj)].append(obj)
        self._count+=1
    
    def withdraw(self, obj):
        '''
        (ChainedHashTable, Object) -> None
        Withdraws the given object from this chained hash table.
        '''
        self._array[self.h(obj)].extract(obj)
        self._count-=1
    
    def __contains__(self, obj):
        '''
        (ChainedHashTable, Object) -> bool
        Returns true if the given object is in this chained hash table.
        '''
        ptr = self._array[self.h(obj)].head
        while ptr is not None:
            if ptr.datum is obj:
                return True
            ptr=ptr.next
        return False
    
    def find(self, obj):
        '''
        (ChainedHashTable, Object) -> Object
        Returns the obj in this hash table
       that matches the given object.
        '''
        ptr=self._array[self.h(obj)].head
        while ptr is not None:
            datum=ptr.datum
            if obj==datum:
                return datum
            ptr=ptr.next
        return None
    
    def accept(self, visitor):
        '''
         (ChainedHashTable, Visitor) -> None
        Makes the given visitor visit all the objects in this hash table.
        '''
        assert isinstance(visitor, Visitor)
        for i, entry in enumerate(self._array):
            ptr=entry.head
            while ptr is not None:
                visitor.visit(ptr.datum)
                if visitor.isDone:
                    return
                ptr=ptr.next
    
    class Iterator(Iterator):
        '''
        Enumerates the._elements of a chained hash table.
        '''
        
        def __init__(self, hashTable):
            '''
            (ChainedHashTable.Iterator, ChainedHashTable) -> None
            Constructs an iterator for the given hash table.
            '''
            super(ChainedHashTable.Iterator, self).__init__(hashTable)
            self._element=None
            self._position=-1
        
        def next(self):
            '''
            (ChainedHashTable.Iterator) -> Object
            Returns the next object in the hash table.
            '''
            if self._element is not None:
                self._element=self._element.next
            if self._element is None:
                self._position+=1
                while self._position<len(self._container):
                    self._element=self._container._array[self._position].head
                    if self._element is not None:
                        break
                    self._position+=1
                if self._position==len(self._container):
                    self._position=-1
            if self._element is None:
                raise StopIteration
            return self._element.datum
    
    def __iter__(self):
        '''
        (ChainedHashTable) -> ChainedHashTable.Iterator
        Returns an iterator for this hash table.
        '''
        return self.Iterator(self)
    
    def _compareTo(self, obj):
        '''
        (ChainedHashTable, ChainedHashTable) -> int

        Compares this hash table with the given hash table.
        '''
        assert isinstance(self, obj.__class__)
        raise NotImplementedError

    @staticmethod
    def main(*argv):
        "ChainedHashTable test program."
        print ChainedHashTable.main.__doc__
        hashTable = ChainedHashTable(57)
        HashTable.test(hashTable)
        return 0

if __name__ == "__main__":
    sys.exit(ChainedHashTable.main(*sys.argv))